package com.jeff.practice;

import java.util.Arrays;

/**
 * @author yaojianfeng
 */
public class LongestSubSequence {


    /**
     * 计算给定数组中最长递增子序列的长度。
     *
     * @param nums 给定的整数数组。该数组用于查找其中最长的递增子序列。
     * @return 返回最长递增子序列的长度。这个值表示在给定数组中能够找到的最长递增子序列的长度。
     */
    public static int longestSubSequence(int[] nums) {

        // 创建一个数组用于存储以每个位置结尾的最长递增子序列的长度。
        int[] maxInt = new int[nums.length];

        // 初始化数组，使得每个位置的最长递增子序列长度都至少为1。
        Arrays.fill(maxInt, 1);

        // 双重循环用于更新每个位置的最长递增子序列长度。
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                // 如果当前数字大于前面的数字，则更新当前位置的最长递增子序列长度。
                if (nums[i] > nums[j]) {
                    maxInt[i] = Integer.max(maxInt[i], maxInt[j] + 1);
                }
            }
            // 打印中间结果用于调试和理解过程。
            System.out.println(Arrays.toString(maxInt));
        }

        // 返回数组中的最大值，即最长递增子序列的长度。
        return Arrays.stream(maxInt).max().getAsInt();
    }


    public static void main(String[] args) {
//        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int[] nums = {3, 9, 2, 5, 4, 7, 101,103, 18};
        System.out.println(longestSubSequence(nums));
        System.out.println(Arrays.toString(nums));
    }



}
